import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] words = new int[]{1,1,1,2,2,3};
        for(int e: s.topKFrequent(words, 2)) {
            System.out.print(e + " ");
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        /**
         * 前k个高频单词
         * 解法1：
         *  使用哈希表计算各单词出现次数，后以值为排序依据进行排倒序，取前k*/
        // 1 预处理
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int e: nums) {
            map.put(e, map.getOrDefault(e, 0) + 1);
        }

        // 2 top K
        // -以值作为排序依据
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        for(Map.Entry<Integer, Integer> e: map.entrySet()) {
            heap.offer(e);
            if(heap.size() > k) {
                heap.poll();
            }
        }

        // 3 返回值
        int[] retArray = new int[k];
        for(int i = 0; i < k; i++) {
            retArray[i] = heap.poll().getKey();
        }
        return retArray;
    }
}
